14.7 KB · ⇊ 8 parts · ⤓ Micron 14.7 KB · ⤓ HTML 59.2 KB

top

Le prix Edsger W. Dijkstra en algorithmique répartie, anciennement prix PoDC de l'article influent, est décerné chaque année, depuis 2000, aux auteurs d'un article dont l'impact est particulièrement important pour la théorie ou la pratique des systèmes distribués depuis au moins dix ans. Remis à l'origine lors de la conférence ACM Principles of Distributed Computing (PoDC), il est, depuis 2007, remis alternativement lors de PoDC les années paires et lors de la conférence EATCS Distributed Computing (DISC) les années impaires, chacune des deux conférences fournissant la moitié de la somme de 2 000 $. Il change de nom en 2003 pour prendre celui de Dijkstra, qui vient de mourir peu après avoir reçu le prix.

• Lauréats

• Liens externes

• Références

| Année | Nom(s) | Article |

|---|---|---|

| 2000 | Leslie Lamport | Time, Clocks, and the Ordering of Events in a Distributed System [ 2 ] |

| 2001 | Michael J. Fischer Nancy Lynch Michael Paterson | Impossibility of Distributed Consensus with One Faulty Process [ 3 ] |

| 2002 | Edsger Dijkstra | Self-stabilizing systems in spite of distributed control [ 4 ] |

| 2003 | Maurice Herlihy | Wait-Free Synchronization [ 5 ] |

| 2004 | Robert G. Gallager Pierre A. Humblet Philip M. Spira | A Distributed Algorithm for Minimum-Weight Spanning Trees [ 6 ] |

| 2005 | Marshall Pease Robert Shostak Leslie Lamport | Reaching agreement in the presence of faults [ 7 ] |

| 2006 | John M. Mellor-Crummey Michael L. Scott (en) | Algorithms for scalable synchronization on shared-memory multiprocessors [ 8 ] |

| 2007 | Cynthia Dwork Nancy Lynch Larry Stockmeyer | Consensus in the presence of partial synchrony [ 9 ] |

| 2008 | Baruch Awerbuch David Peleg | Sparse Partitions [ 10 ] |

| 2009 | Joseph Halpern Yoram Moses | Knowledge and Common Knowledge in a Distributed Environment [ 11 ] |

| 2010 | Tushar Deepak Chandra Sam Toueg Vassos Hadzilacos | Unreliable Failure Detectors for Reliable Distributed Systems The Weakest Failure Detector for Solving Consensus |

| 2011 | Hagit Attiya Amotz Bar-Noy Danny Dolev | Sharing Memory Robustly in Message-Passing Systems |

| 2012 | Maurice Herlihy J. Eliot B. Moss Nir Shavit Dan Touitou | Transactional memory Software transactional memory |

| 2013 | Nati Linial | Locality in distributed graph algorithms [ 12 ] |

| 2014 | K. Mani Chandy (en) et Leslie Lamport | The Snapshot algorithm to get a consistent picture of the global state of a system [ 13 ] |

| 2015 | Michael Ben-Or | Another Advantage of Free Choice: Completely Asynchronous Agreement Protocols [ 14 ] |

| 2015 | Michael O. Rabin | Randomized Byzantine Generals [ 15 ] |

| 2016 | Noga Alon , László Babai et Alon Itai | A Fast and Simple Randomized Parallel Algorithm for the Maximal Independent Set Problem [ 16 ] |

| 2016 | Michael Luby | Simple Parallel Algorithm for the Maximal Independent Set Problem [ 17 ] |

| 2017 | Elizabeth Borowsky et Eli Gafni | Generalized FLP impossibility result for t-resilient asynchronous computations [ 18 ] |

| 2018 | Bowen Alpern et Fred B. Schneider | Defining liveness [ 19 ] |

| 2019 | Alessandro Panconesi et Aravind Srinivasan | Randomized Distributed Edge Coloring via an Extension of the Chernoff–Hoeffding Bounds [ 20 ] |

| 2020 | Dana Angluin , James Aspnes (en) , Zoe Diamadi, Michael J. Fischer , et Rene Peralta | Computation in networks of passively mobile finite-state sensors [ 21 ] |

| 2021 | Paris C. Kanellakis et Scott A. Smolka (en) | CCS Expressions, Finite State Processes, and Three Problems of Equivalence [ 22 ] |

| 2022 | Maged M. Michael | Safe Memory Reclamation for Dynamic Lock-Free Objects Using Atomic Reads and Writes [ 23 ] |

| 2022 | Maurice Herlihy , Victor Luchangco et Mark Moir | The Repeat Offender Problem: A Mechanism for Supporting Dynamic-Sized, Lock-Free Data Structures [ 24 ] |

| 2023 | Michael Ben-Or (en) , Shafi Goldwasser et Avi Wigderson | Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation [ 25 ] . |

| 2023 | David Chaum , Claude Crépeau et Ivan Damgård | Multiparty Unconditionally Secure Protocols [ 26 ] . |

| 2023 | Tal Rabin et Michael Ben-Or (he) | Verifiable Secret Sharing and Multiparty Protocols with Honest Majority [ 27 ] . |

| 2024 | Nicola Santoro et Peter Widmayer | Time is Not a Healer [ 28 ] |

• (en) Page officielle de l'EATCS pour le prix Dijkstra

• (en) Page officielle de l'ACM (PODC) pour le prix Dijkstra

cite-note-11. « Dijkstra Prize », EATCS (consulté le 15 mars 2010)

cite-note-22. lamport1978leslie-lamport1978(en) Leslie Lamport, « Time, Clocks, and the Ordering of Events in a Distributed System », Communications of the ACM, vol. 21, no 7,‎ 1978, p. 558-565 (lire en ligne [PDF])

cite-note-33. fischerlynchpaterson1985michael-j-fischernancy-a-lynchmichael-s-paterson1985(en) Michael J. Fischer, Nancy A. Lynch et Michael S. Paterson, « Impossibility of Distributed Consensus with One Faulty Process », Journal of the ACM, vol. 32, no 2,‎ avril 1985, p. 374-382 (lire en ligne [PDF])

cite-note-44. dijkstra1974edsger-wybe-dijkstra1974(en) Edsger Wybe Dijkstra, « Self-stabilizing systems in spite of distributed control », Communications of the ACM, vol. 17, no 11,‎ 1974, p. 643-644 (lire en ligne [PDF])

cite-note-55. herlihy1991maurice-herlihy1991(en) Maurice Herlihy, « Wait-Free Synchronization », ACM Transactions on Programming Languages and Systems, vol. 13, no 1,‎ janvier 1991, p. 124-149 (lire en ligne [PDF])

cite-note-66. gallagherhumbletspira1983robert-g-gallagherpierre-a-humbletphilip-m-spira1983(en) Robert G. Gallagher, Pierre A. Humblet et Philip M. Spira, « A Distributed Algorithm for Minimum-Weight Spanning Trees », ACM Transactions on Programming Languages and Systems, vol. 5, no 1,‎ janvier 1983, p. 66-77 (lire en ligne [PDF])

cite-note-77. peaseshostaklamport1980marshall-peaserobert-shostakleslie-lamport1980(en) Marshall Pease, Robert Shostak et Leslie Lamport, « Reaching agreement in the presence of faults », Journal of the ACM, vol. 27, no 1,‎ avril 1980, p. 228-234 (lire en ligne [PDF])

cite-note-88. mellor-crummeyscott1991john-m-mellor-crummeymichael-l-scott1991(en) John M. Mellor-Crummey et Michael L. Scott, « Algorithms for scalable synchronization on shared-memory multiprocessors », ACM Transactions on Computer Systems, vol. 9, no 1,‎ 1991 (lire en ligne [PDF])

cite-note-99. dworklynchstockmeyer1988cynthia-dworknancy-lynchlarry-stockmeyer1988(en) Cynthia Dwork, Nancy Lynch et Larry Stockmeyer, « Consensus in the presence of partial synchrony », Journal of the ACM, vol. 35, no 2,‎ avril 1988, p. 288-323 (lire en ligne [PDF])

cite-note-1010. awerbuchpeleg1990baruch-awerbuchdavid-peleg1990(en) Baruch Awerbuch et David Peleg, « Sparse Partitions », Proceedings of the Annual Symposium on Foundations of Computer Science (FOCS),‎ 1990, p. 503-513 (lire en ligne [PDF])

cite-note-1111. halpernmoses1990joseph-halpernyoram-moses1990(en) Joseph Halpern et Yoram Moses, « Knowledge and Common Knowledge in a Distributed Environment », Journal of the ACM, vol. 37, no 3,‎ 1990, p. 549-587 (lire en ligne [PDF])

cite-note-1212. linial1992nathan-linial1992(en) Nathan Linial, « Locality in Distributed Graph Algorithms », SIAM Journal on Computing, vol. 21, no 1,‎ 1992, p. 193-201.

cite-note-1313. mani-chandylamport1985k-mani-chandyleslie-lamport1985(en) K. Mani Chandy et Leslie Lamport, « Distributed Snapshots: Determining Global States of Distributed Systems », ACM Trans. Comput. Syst., vol. 3, no 1,‎ 1985, p. 63-75

cite-note-1414. ben-or1983michael-ben-or1983(en) Michael Ben-Or, « Another Advantage of Free Choice: Completely Asynchronous Agreement Protocols », dans Proceedings of the Second ACM Symposium on Principles of Distributed Computing, 1983, p. 27-30

cite-note-1515. rabin1983michael-o-rabin1983(en) Michael O. Rabin, « Randomized Byzantine Generals », dans Proceedings of Twenty-Fourth IEEE Annual Symposium on Foundations of Computer Science, 1983, p. 403-409

cite-note-1616. alonbabaiitai1986noga-alonl-szl-babaialon-itai1986Noga Alon, László Babai et Alon Itai, « A Fast and Simple Randomized Parallel Algorithm for the Maximal Independent Set Problem », J. Algorithms, vol. 7, no 4,‎ 1986, p. 567-583 (DOI 10.1016/0196-6774(86)90019-2).

cite-note-1717. luby1986michael-luby1986Michael Luby, « A Simple Parallel Algorithm for the Maximal Independent Set Problem », SIAM J. Comput., vol. 15, no 4,‎ 1986, p. 1036-1053 (DOI 10.1137/0215074).

cite-note-1818. borowskygafni1993elizabeth-borowskyeli-gafni1993Elizabeth Borowsky et Eli Gafni, « Generalized FLP impossibility result for t-resilient asynchronous computations, », dans Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, May 16-18, 1993, San Diego, CA, USA, 1993, p. 91--100

cite-note-1919. alpernschneider1985bowen-alpernfred-b-schneider1985Bowen Alpern et Fred B. Schneider, « Defining Liveness », Inf. Process. Lett., vol. 21, no 4,‎ 1985, p. 181-185 (DOI 10.1016/0020-0190(85)90056-0)

cite-note-2020. panconesisrinivasan1997alessandro-panconesiaravind-srinivasan1997Alessandro Panconesi et Aravind Srinivasan, « Randomized Distributed Edge Coloring via an Extension of the Chernoff–Hoeffding Bounds », SIAM Journal on Computing, vol. 26, no 2,‎ 1997, p. 350–368

cite-note-2121. angluinaspnesdiamadifischer2006dana-angluinjames-aspneszoe-diamadimichael-j-fischer2006Dana Angluin, James Aspnes, Zoe Diamadi, Michael J. Fischer et Rene Peralta, « Computation in networks of passively mobile finite-state sensors », Distributed Computing, vol. 18, no 4,‎ 2006, p. 235-253

cite-note-2222. kanellakissmolka1990paris-c-kanellakisscott-a-smolka1990Paris C. Kanellakis et Scott A. Smolka, « CCS Expressions, Finite State Processes, and Three Problems of Equivalence ` », Inf. Comput., vol. 86, no 1,‎ 1990, p. 43-68

cite-note-2323. michael2002maged-m-michael2002Maged M. Michael, « Safe Memory Reclamation for Dynamic Lock-Free Objects Using Atomic Reads and Writes », Proceedings of the 22nd ACM Symposium on Principles of Distributed Computing (PODC),‎ 2002, p. 21–30 (DOI 10.1145/571825.571829).

cite-note-2424. herlihy-victor-luchangco-et-mark-moir2002maurice-herlihy-victor-luchangco-et-mark-moir2002Maurice Herlihy, Victor Luchangco et Mark Moir, « The Repeat Offender Problem: A Mechanism for Supporting Dynamic-Sized, Lock-Free Data Structures », Lecture Notes in Computer Science, Toulouse, vol. 2508 « Proceedings of the 16th International Symposium on Distributed Computing (DISC) »,‎ octobre 2002, p. 339–353 (DOI 10.1007/3-540-36108-1_23).

cite-note-2525. ben-orgoldwasserwigderson2019michael-ben-orshafi-goldwasseravi-wigderson2019Michael Ben-Or, Shafi Goldwasser et Avi Wigderson, « Completeness theorems for non-cryptographic fault-tolerant distributed computation », Providing Sound Foundations for Cryptography, Association for Computing Machinery,‎ 4 octobre 2019, p. 351–371 (ISBN 978-1-4503-7266-4, DOI 10.1145/3335741.3335756).

cite-note-2626. 1988« Multiparty Unconditionally Secure Protocols », Proceedings of the 20th ACM Symposium on Theory of Computing (STOC),‎ mai 1988, p. 11-19.

cite-note-2727. 1989« Verifiable Secret Sharing and Multiparty Protocols with Honest Majority », Proceedings of the 21st ACM Symposium on Theory of Computing (STOC),‎ mai 1989, p. 73-85.

cite-note-2828. santorowidmayer1989nicola-santoropeter-widmayer1989Nicola Santoro et Peter Widmayer, « Time is Not a Healer », Proceedings of the 6th Annual Symposium on Theoretical Aspects of Computer Science,‎ 1989, p. 304–313.

• Portail de l’informatique

• Portail des récompenses et des distinctions

• Portail de l'informatique théorique